An integrated circuit (IC) comprises cells of similar and/or various sizes, and connections between or among the cells. A cell includes several pins interconnected by wires to pins of one or more other cells. A net includes a set of pins connected by wires in order to form connections between or among the pins. An IC may include a set of nets. A design netlist specifies the connections between the pins.
Design engineers design IC's by transforming circuit descriptions of the IC's into geometric descriptions, called layouts. To create layouts, design engineers typically use electronic design automation (EDA) applications. These applications provide sets of computer-based tools for creating, editing, and analyzing IC design layouts.
EDA applications create layouts by using geometric shapes that represent different materials and devices on IC's. For instance, EDA tools commonly use rectilinear lines to represent the wire segments that interconnect the IC components. These tools also represent electronic and circuit IC components as geometric objects with varying shapes and sizes.
The IC design process entails various operations. Some of the physical-design operations that EDA applications commonly perform to obtain the IC layouts are: (1) circuit partitioning, which partitions a circuit if the circuit is too large for a single chip; (2) floor planning, which finds the alignment and relative orientation of the circuit modules; (3) placement, which determines more precisely the positions of the circuit components; (4) routing, which completes the interconnects between or among the circuit components; and (5) verification, which checks the layout to ensure that it meets design and functional requirements.
Routing is a key operation in the physical design cycle. It is generally divided into two phases: global routing and detailed routing. For each net, global routing generates a routing topology that includes an approximate routing path for the interconnect lines that are to connect the pins of the net. After the routing topology has been created, detailed routing creates specific individual routes for each net.
Due to the large number of nets in the netlist, it typically takes a long time for conventional routers to finish the connection task. In addition, the connections may be too numerous and/or overcrowded, such that conventional routers fail to finish the routing, particularly generating interconnections, without violating one or more routing constraints (e.g., design-rule constraints and performance constraints). For example, a hierarchical IC design may include one or more partitions and a routing constraint that limits the routing path of nets in the design to only a single entry into each partition (e.g., a routing path may intersect with partition boundaries only once) to reduce design, device, and manufacturing costs. However, conventional routing methods are generally not partition aware, and as such, cannot guarantee a single-entry-violation-free routing result. In other words, the conventional routing methods result in routing topologies that may have multiple entries to a single partition thereby creating a violation to the single-entry constraint.